package com.yanceysong.codetop.s1_s10;

import java.util.Arrays;

public class S8_Mid_补充题4_手撕快速排序 {
    /**
     * .S8_Mid_补充题4_手撕快速排序
     * .<p>
     * .快速排序（Quick Sort）是一种基于分治思想的高效排序算法。
     * .它通过选择一个基准元素，将数组分为两部分，使得左边的元素都小于基准，右边的元素都大于基准。
     * .然后递归地对左右两部分进行排序。
     * .<p>
     * .核心标签：排序、分治、递归、数组
     * .<p>
     * .算法原理：
     * .1. 选择基准（Pivot）：从数组中选择一个元素作为基准
     * .2. 分区（Partition）：重新排列数组，使得：
     * .   - 所有小于基准的元素都在基准左边
     * .   - 所有大于基准的元素都在基准右边
     * .   - 基准元素在最终排序后的正确位置
     * .3. 递归排序：递归地对左右两个子数组进行快速排序
     * .<p>
     * .分区过程详解（双指针法）：
     * .- 选择最右边的元素作为基准
     * .- 使用两个指针：i（慢指针）和 j（快指针）
     * .- i 指向小于基准的区域的边界
     * .- j 遍历数组，寻找小于基准的元素
     * .- 当找到小于基准的元素时，交换 i 和 j 位置的元素，i 右移
     * .- 最后将基准元素放到正确位置（i 的位置）
     * .<p>
     * .关键洞察：
     * .1. 快速排序是原地排序算法，不需要额外的存储空间（除了递归栈）
     * .2. 快速排序是不稳定的排序算法（相同元素的相对位置可能改变）
     * .3. 基准的选择对性能影响很大，随机选择或三数取中可以避免最坏情况
     * .4. 平均时间复杂度是 O(n log n)，但最坏情况是 O(n²)
     * .5. 快速排序在实际应用中通常比其他 O(n log n) 算法更快
     * .<p>
     * .图解示例：arr = [10, 7, 8, 9, 1, 5]
     * .<p>
     * .第一轮分区（基准 = 5）：
     * .<p>
     * .初始状态：
     * .[10, 7, 8, 9, 1, 5]
     * . i                pivot
     * . j
     * .<p>
     * .j=0: arr[0]=10 > 5，不交换，j++
     * .[10, 7, 8, 9, 1, 5]
     * . i                pivot
     * .    j
     * .<p>
     * .j=1: arr[1]=7 > 5，不交换，j++
     * .[10, 7, 8, 9, 1, 5]
     * . i                pivot
     * .       j
     * .<p>
     * .j=2: arr[2]=8 > 5，不交换，j++
     * .[10, 7, 8, 9, 1, 5]
     * . i                pivot
     * .          j
     * .<p>
     * .j=3: arr[3]=9 > 5，不交换，j++
     * .[10, 7, 8, 9, 1, 5]
     * . i                pivot
     * .             j
     * .<p>
     * .j=4: arr[4]=1 < 5，交换 arr[i] 和 arr[j]，i++
     * .[1, 7, 8, 9, 10, 5]
     * .    i             pivot
     * .                j
     * .<p>
     * .遍历结束，将基准放到正确位置（交换 arr[i] 和 arr[pivot]）
     * .[1, 5, 8, 9, 10, 7]
     * .    ↑
     * .  基准在正确位置
     * .<p>
     * .递归排序左右两部分：
     * .左部分：[1]（已排序）
     * .右部分：[8, 9, 10, 7]
     * .<p>
     * .第二轮分区（右部分，基准 = 7）：
     * .<p>
     * .[8, 9, 10, 7]
     * . i         pivot
     * . j
     * .<p>
     * .j=0: arr[0]=8 > 7，不交换
     * .j=1: arr[1]=9 > 7，不交换
     * .j=2: arr[2]=10 > 7，不交换
     * .<p>
     * .将基准放到正确位置
     * .[7, 9, 10, 8]
     * . ↑
     * .基准在正确位置
     * .<p>
     * .递归排序右部分：[9, 10, 8]
     * .<p>
     * .第三轮分区（基准 = 8）：
     * .<p>
     * .[9, 10, 8]
     * . i      pivot
     * . j
     * .<p>
     * .j=0: arr[0]=9 > 8，不交换
     * .j=1: arr[1]=10 > 8，不交换
     * .<p>
     * .将基准放到正确位置
     * .[8, 10, 9]
     * . ↑
     * .基准在正确位置
     * .<p>
     * .递归排序右部分：[10, 9]
     * .<p>
     * .第四轮分区（基准 = 9）：
     * .<p>
     * .[10, 9]
     * . i   pivot
     * . j
     * .<p>
     * .j=0: arr[0]=10 > 9，不交换
     * .<p>
     * .将基准放到正确位置
     * .[9, 10]
     * . ↑
     * .基准在正确位置
     * .<p>
     * .最终排序结果：[1, 5, 7, 8, 9, 10]
     * .<p>
     * .分区过程的详细图解：
     * .<p>
     * .原始数组：[10, 7, 8, 9, 1, 5]，基准 = 5
     * .<p>
     * .小于基准的区域 | 大于基准的区域 | 未处理 | 基准
     * .[              |                |        | 5   ]
     * . ↑                                        ↑
     * . i                                      pivot
     * .<p>
     * .遍历过程：
     * .j 遇到 1（< 5），交换到左边
     * .[1 | 7, 8, 9, 10 | 5]
     * .    ↑              ↑
     * .    i            pivot
     * .<p>
     * .最后将基准放到 i 的位置
     * .[1 | 5 | 8, 9, 10, 7]
     * .     ↑
     * .   基准在正确位置
     * .<p>
     * .快速排序的递归树：
     * .<p>
     * .               [10, 7, 8, 9, 1, 5]
     * .                       ↓
     * .             分区（基准=5）
     * .                       ↓
     * .           [1] | 5 | [8, 9, 10, 7]
     * .            ↓         ↓
     * .          已排序   分区（基准=7）
     * .                       ↓
     * .                 [7] | [9, 10, 8]
     * .                  ↓         ↓
     * .                已排序  分区（基准=8）
     * .                             ↓
     * .                       [8] | [10, 9]
     * .                        ↓         ↓
     * .                      已排序  分区（基准=9）
     * .                                   ↓
     * .                             [9] | [10]
     * .                              ↓     ↓
     * .                            已排序 已排序
     * .<p>
     * .时间复杂度：
     * .- 最好情况：O(n log n)，每次分区都将数组平均分成两部分
     * .- 平均情况：O(n log n)
     * .- 最坏情况：O(n²)，每次分区都极度不平衡（如已排序数组）
     * .<p>
     * .空间复杂度：O(log n)
     * .- 递归调用栈的深度
     * .- 最坏情况：O(n)（退化为链式递归）
     * .<p>
     * .快速排序的优缺点：
     * .<p>
     * .优点：
     * .1. 平均性能优秀，实际应用中通常最快
     * .2. 原地排序，空间复杂度低
     * .3. 缓存友好（局部性好）
     * .<p>
     * .缺点：
     * .1. 不稳定排序（相同元素的相对位置可能改变）
     * .2. 最坏情况性能差（O(n²)）
     * .3. 递归实现可能导致栈溢出（可以改为迭代实现）
     * .<p>
     * .优化技巧：
     * .1. 三数取中法选择基准（首、中、尾三个元素的中位数）
     * .2. 随机选择基准
     * .3. 小数组使用插入排序
     * .4. 尾递归优化
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSortHelper(arr, 0, arr.length - 1);
    }

    /**
     * .快速排序递归辅助方法
     * .@param arr   待排序数组
     * .@param left  左边界索引
     * .@param right 右边界索引
     */
    private static void quickSortHelper(int[] arr, int left, int right) {
        // 递归终止条件：当左边界大于等于右边界时，子数组已排序
        if (left >= right) {
            return;
        }

        // 分区操作，返回基准元素的最终位置
        int pivotIndex = partition(arr, left, right);

        // 递归排序左半部分（基准左边的元素）
        quickSortHelper(arr, left, pivotIndex - 1);

        // 递归排序右半部分（基准右边的元素）
        quickSortHelper(arr, pivotIndex + 1, right);
    }

    /**
     * .分区操作（双指针法）
     * .将数组分为两部分：小于基准的元素在左边，大于基准的元素在右边
     * <p>
     * .@param arr   待分区数组
     * .@param left  左边界索引
     * .@param right 右边界索引
     * .@return 基准元素的最终位置索引
     */
    private static int partition(int[] arr, int left, int right) {
        // 选择最右边的元素作为基准
        int pivot = arr[right];

        // i 指向小于基准的区域的边界（最后一个小于基准的元素的位置）
        int i = left - 1;

        // j 遍历数组，寻找小于基准的元素
        for (int j = left; j < right; j++) {
            // 如果当前元素小于或等于基准
            if (arr[j] <= pivot) {
                // 将 i 右移，扩大小于基准的区域
                i++;
                // 将当前元素交换到小于基准的区域
                swap(arr, i, j);
            }
        }

        // 将基准元素放到正确位置（i+1 的位置）
        // 此时 i+1 是第一个大于基准的元素的位置
        swap(arr, i + 1, right);

        // 返回基准元素的最终位置
        return i + 1;
    }

    /**
     * .交换数组中两个位置的元素
     * <p>
     * .@param arr 数组
     * .@param i   第一个位置
     * .@param j   第二个位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println("=== 快速排序测试开始 ===");

        // 测试1: 基本测试 [10, 7, 8, 9, 1, 5]
        System.out.println("\n--- 测试1: 基本测试 ---");
        testCase1();

        // 测试2: 已排序数组（升序）
        System.out.println("\n--- 测试2: 已排序数组（升序）---");
        testSortedArray();

        // 测试3: 逆序数组
        System.out.println("\n--- 测试3: 逆序数组 ---");
        testReverseSortedArray();

        // 测试4: 包含重复元素
        System.out.println("\n--- 测试4: 包含重复元素 ---");
        testDuplicateElements();

        // 测试5: 单元素数组
        System.out.println("\n--- 测试5: 单元素数组 ---");
        testSingleElement();

        // 测试6: 两个元素
        System.out.println("\n--- 测试6: 两个元素 ---");
        testTwoElements();

        // 测试7: 所有元素相同
        System.out.println("\n--- 测试7: 所有元素相同 ---");
        testAllSameElements();

        // 测试8: 包含负数
        System.out.println("\n--- 测试8: 包含负数 ---");
        testNegativeNumbers();

        // 测试9: 包含零
        System.out.println("\n--- 测试9: 包含零 ---");
        testWithZero();

        // 测试10: 大数组
        System.out.println("\n--- 测试10: 大数组 ---");
        testLargeArray();

        // 测试11: 空数组
        System.out.println("\n--- 测试11: 空数组 ---");
        testEmptyArray();

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 基本测试 [10, 7, 8, 9, 1, 5]
     * .期望输出：[1, 5, 7, 8, 9, 10]
     */
    private static void testCase1() {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int[] expected = {1, 5, 7, 8, 9, 10};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试1失败";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 已排序数组（升序）[1, 2, 3, 4, 5]
     * .期望输出：[1, 2, 3, 4, 5]
     */
    private static void testSortedArray() {
        int[] arr = {1, 2, 3, 4, 5};
        int[] expected = {1, 2, 3, 4, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试2失败";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 逆序数组 [5, 4, 3, 2, 1]
     * .期望输出：[1, 2, 3, 4, 5]
     */
    private static void testReverseSortedArray() {
        int[] arr = {5, 4, 3, 2, 1};
        int[] expected = {1, 2, 3, 4, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试3失败";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 包含重复元素 [4, 2, 4, 1, 3, 2]
     * .期望输出：[1, 2, 2, 3, 4, 4]
     */
    private static void testDuplicateElements() {
        int[] arr = {4, 2, 4, 1, 3, 2};
        int[] expected = {1, 2, 2, 3, 4, 4};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试4失败";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单元素数组 [42]
     * .期望输出：[42]
     */
    private static void testSingleElement() {
        int[] arr = {42};
        int[] expected = {42};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试5失败";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 两个元素 [2, 1]
     * .期望输出：[1, 2]
     */
    private static void testTwoElements() {
        int[] arr = {2, 1};
        int[] expected = {1, 2};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试6失败";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 所有元素相同 [5, 5, 5, 5, 5]
     * .期望输出：[5, 5, 5, 5, 5]
     */
    private static void testAllSameElements() {
        int[] arr = {5, 5, 5, 5, 5};
        int[] expected = {5, 5, 5, 5, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试7失败";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 包含负数 [-5, 3, -1, 7, -9, 2]
     * .期望输出：[-9, -5, -1, 2, 3, 7]
     */
    private static void testNegativeNumbers() {
        int[] arr = {-5, 3, -1, 7, -9, 2};
        int[] expected = {-9, -5, -1, 2, 3, 7};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试8失败";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 包含零 [0, -1, 5, 0, 3, -2]
     * .期望输出：[-2, -1, 0, 0, 3, 5]
     */
    private static void testWithZero() {
        int[] arr = {0, -1, 5, 0, 3, -2};
        int[] expected = {-2, -1, 0, 0, 3, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试9失败";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 大数组（100个元素）
     * .期望输出：升序排列
     */
    private static void testLargeArray() {
        int[] arr = new int[100];
        // 填充随机数据（使用固定种子以便验证）
        for (int i = 0; i < 100; i++) {
            arr[i] = 100 - i; // 逆序
        }

        System.out.println("原始数组: [100, 99, 98, ..., 3, 2, 1]");
        quickSort(arr);
        System.out.print("排序后:   [");
        for (int i = 0; i < 10; i++) {
            System.out.print(arr[i] + (i < 9 ? ", " : ""));
        }
        System.out.println(", ..., " + arr[99] + "]");

        // 验证数组是否已排序
        for (int i = 0; i < arr.length - 1; i++) {
            assert arr[i] <= arr[i + 1] : "数组未正确排序";
        }

        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 空数组
     * .期望输出：[]
     */
    private static void testEmptyArray() {
        int[] arr = {};
        int[] expected = {};

        System.out.println("原始数组: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试11失败";
        System.out.println("✓ 测试11通过");
    }
}
